/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec
{
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {
        stringstream ss;
        function<void(TreeNode *)> dfs = [&](TreeNode *t)
        {
            if (t == nullptr)
            {
                ss << "# ";
            }
            else
            {
                ss << t->val << " ";
                dfs(t->left);
                dfs(t->right);
            }
        };
        dfs(root);
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {
        stringstream ss(data);
        string s;
        TreeNode pseudoRoot;
        bool left = true;
        stack<TreeNode *> st;
        st.push(&pseudoRoot);
        while (ss >> s)
        {
            if (s == "#")
            {
                if (left)
                {
                    left = false;
                }
                else
                {
                    st.pop();
                }
            }
            else
            {
                int val = stoi(s);
                TreeNode *t = new TreeNode(val);
                if (left)
                {
                    st.top()->left = t;
                }
                else
                {
                    st.top()->right = t;
                    st.pop();
                }
                st.push(t);
                left = true;
            }
        }

        return pseudoRoot.left;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;